#include <iostream>
#include <stack>

#include "common/utils.hpp"

// 借助栈迭代
bool hasPathSum(TreeNode* root, int targetSum) {
    std::stack<std::pair<TreeNode*, int>> st;
    if (root == nullptr) return false;

    // 记录路径到这个节点的和
    st.push(std::pair<TreeNode*, int>(root, root->val));
    while(!st.empty()) {
        std::pair<TreeNode*, int> pNode = st.top();
        st.pop();

        if (pNode.first->left == nullptr && pNode.first->right == nullptr) {
            if (pNode.second == targetSum) return true;
        }

        if (pNode.first->left != nullptr) {
            st.push(std::pair<TreeNode*, int>(pNode.first->left, pNode.second + pNode.first->left->val));
        }

        if (pNode.first->right != nullptr) {
            st.push(std::pair<TreeNode*, int>(pNode.first->right, pNode.second + pNode.first->right->val));
        }
    }

    return false;
}

extern TreeNode* commonRoot;

int main() {
    int ret = hasPathSum(commonRoot, 40);
    std::cout << "res: " << ret << "\n";
}